233. Number of Digit One

1. Question

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

2. Examples

Example 1:

Input: n = 13
Output: 6

Example 2:

Input: n = 0
Output: 0

3. Constraints

• 0 <= n <= 10⁹

4. References

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/number-of-digit-one 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

5. Solutions

class Solution {
    public int countDigitOne(int n) {
        /**整体思路，计算每一位的1然后相加 */
        int ans = 0;
        int right = 0; // 每一位右侧的数
        int base = 1; // 记录每一位左侧数需要乘上的基数
        int cur = 0; // 记录当前位数
        int old = 0; // 记录上一轮的余数
        while (n > 0) {
            cur = n % 10;
            right += (base / 10) * old;
            n /= 10;
            if (cur == 1) {
                ans += n * base + right + 1;
            }
            if (cur == 0) {
                ans += n * base;
            }
            if (cur > 1) {
                ans += n * base + base;
            }
            base *= 10;
            old = cur;
        }
        return ans;
    }
}